Graph minors and linkages

Bollobás and Thomason showed that every 22k‐connected graph is k‐linked. Their result used a dense graph minor. In this paper, we investigate the ties between small graph minors and linkages. In particular, we show that a 6‐connected graph with a K minor is 3‐linked. Further, we show that a 7‐connected graph with a K minor is (2,5)‐linked. Finally, we show that a graph of order n and size at least 7n?29 contains a K minor. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 75–91, 2005     

The Size and Composition of a Road Transport Fleet

The paper starts with a discussion of the simple fleet size problem. It is shown that this simple problem can be formulated as a linear program.The second part of the paper consists of an actual case study. The fleet concerned is faced with highly seasonal demand which can be met by the firm's own vehicles or by outside hire. There are two types of vehicle, both of which are available in six different sizes. Linear programming was used to find the optimum size and composition of the company fleet. The results, which were substantially implemented, recommended a smaller company fleet and concentration on larger and more flexible vehicles.     

Long-wavelength excitations in a Bose gas at zero temperature

The long-wavelength excitations in a simple model of a dilute Bose gas at zero temperature are investigated from a purely microscopic viewpoint. The role of the interaction and the effects of the condensate are emphasized in a dielectric formulation, in which the response functions are expressed in terms of regular functions that do not involve an isolated single-interaction line nor an isolated single-particle line. Local number conservation is incorporated into the formulation by the generalized Ward identities, which are used to express the regular functions involving the density in terms of regular functions involving the longitudinal current. A perturbation expansion is then developed for the regular functions, producing to a given order in the perturbation expansion an elementary excitation spectrum without a gap and simultaneously response functions that obey local number conservation and related sum rules.Explicit results to the first order beyond the Bogoliubov approximation in a simple one-parameter model are obtained for the elementary excitation spectrum ω_k, the dynamic structure function $\text{S}$(k, ω), the associated structure function $\text{S}$_m(k), and the one-particle spectral function $\text{A}$(k, ω), as functions of the wavevector k and frequency ω. These results display the sharing of the gapless spectrum ω_k by the various response functions and are used to confirm that the sum rules of interest are satisfied. It is shown that ω_k and some of the $\text{S}$_m(k) are not analytic functions of k in the long wavelength limit. The dynamic structure function $\text{S}$(k, ω) can be conveniently separated into three parts: a one-phonon term which exhausts the f sum rule, a backflow term, and a background term. The backflow contribution to the static structure function $\text{S}$₀(k) leads to the breakdown of the one-phonon Feynman relation at order k³. Both $\text{S}$(k, ω) and $\text{A}$(k, ω) display broad backgrounds because of two-phonon excitations. Simple arguments are given to indicate that some of the qualitative features found for various physical quantities in the first-order model calculation might also be found in superfluid helium.     

Exact penalty functions in nonlinear programming

In this paper some new theoretic results on piecewise differentiable exact penalty functions are presented. Sufficient conditions are given for the existence of exact penalty functions for inequality constrained problems more general than concave and several classes of such functions are presented.This research was partially supported by a grant from the Office of Naval Research; contract number N00014-67-A-0321-0003 (NR047-095).     

Tetrapyrrole singlet excited state quenching by carotenoids in an artificial photosynthetic antenna

Two artificial photosynthetic antenna models consisting of a Si phthalocyanine (Pc) bearing two axially attached carotenoid moieties having either 9 or 10 conjugated double bonds are used to illustrate some of the function of carotenoids in photosynthetic membranes. Both models studied in toluene, methyltetrahydrofuran, and benzonitrile exhibited charge separated states of the type C*+-Pc*- confirming that the quenching of the Pc S1 state is due to photoinduced electron transfer. In hexane, the Pc S1 state of the 10 double bond carotenoid-Pc model was slightly quenched but the C*+-Pc*- transient was not spectroscopically detected. A semiclassical analysis of the data in hexane at temperatures ranging from 180 to 320 K was used to demonstrate that photoinduced electron transfer could occur. The model bearing the 10 double bond carotenoids exhibits biexponential fluorescence decay in toluene and in hexane, which is interpreted in terms of an equilibrium mixture of two isomers comprising s-cis and s-trans conformers of the carotenoid. The shorter fluorescence lifetime is associated with an s-cis carotenoid conformer where the close approach between the donor and acceptor moieties provides through-space electronic coupling in addition to the through-bond component.     

Second-Order Optimality and Beyond: Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization

High-order optimality conditions for convexly constrained nonlinear optimization problems are analysed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order \(\epsilon \)-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that if derivatives of the objective function up to order \(q \ge 1\) can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most \(O(\epsilon ^{-(q+1)})\) evaluations of f and its derivatives to compute an \(\epsilon \)-approximate qth-order critical point. This provides the first evaluation complexity result for critical points of arbitrary order in nonlinear optimization. An example is discussed, showing that the obtained evaluation complexity bounds are essentially sharp.     

Fragmentation of 2,2,2-triphenylethoxychlorocarbene: evidence for ultrafast fragmentation-rearrangement in excited diazirines

[reaction: see text] Photolysis of 3-(2,2,2-triphenylethoxy)-3-chlorodiazirine gives 2,2,2-triphenylethoxychlorocarbene which fragments with 1,2-phenyl migration and loss of CO and Cl(-) to yield the 1,1,2-triphenylethyl cation and thence 1,1,2-triphenylethene by proton loss. However, ps and fs laser flash photolysis provides evidence that up to 25% of the alkene product stems from carbocation that arises directly from excited diazirine rather than from the carbene.     

On solving trust-region and other regularised subproblems in optimization

The solution of trust-region and regularisation subproblems that arise in unconstrained optimization is considered. Building on the pioneering work of Gay, Moré and Sorensen, methods that obtain the solution of a sequence of parametrized linear systems by factorization are used. Enhancements using high-order polynomial approximation and inverse iteration ensure that the resulting method is both globally and asymptotically at least superlinearly convergent in all cases, including the notorious hard case. Numerical experiments validate the effectiveness of our approach. The resulting software is available as packages TRS{\tt TRS} and RQS{\tt RQS} as part of the GALAHAD optimization library, and is especially designed for large-scale problems.